Definition

Define the complexity class, TFNP (total functions from NP), as all total search problems in FNP.

Notes

  • could also be called F(NP∩coNP)\mathrm{F}(\mathrm{NP} \cap \mathrm{coNP})

References

  1. N. Megiddo and C. H. Papadimitriou, “On total functions, existence theorems and computational complexity,” Theoretical Computer Science, vol. 81, no. 2, pp. 317–324, Apr. 1991, doi: 10.1016/0304-3975(91)90200-L.
  2. N. Bitansky et al., “PPAD is as hard as LWE and iterated squaring,” 2022, Cryptology ePrint Archive: cryptoeprint:2022/1272. [Online]. Available: https://eprint.iacr.org/2022/1272
  3. https://en.wikipedia.org/wiki/TFNP